#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
private:
    TreeNode * createNode(int val)
    {
        return new TreeNode(val);
    }

    TreeNode * recursion(vector<int>& inorder, vector<int>& postorder)
    {
        if(inorder.empty() && postorder.empty())
        {
            return nullptr;
        }
        int midValue = *(postorder.end() - 1);
        auto mid = createNode(midValue);
        if(postorder.size() == 1)
        {
            return mid;
        }

        vector<int> inorderLeft;
        vector<int> inorderRight;
        bool afterMid = false;
        for(int i = 0; i < inorder.size(); i++)
        {
            if(inorder[i] == midValue)
            {
                afterMid = true;
                continue;
            }
            if(afterMid)
            {
                inorderRight.push_back(inorder[i]);
            }
            else
            {
                inorderLeft.push_back(inorder[i]);
            }
        }
        vector<int> postorderLeft(postorder.begin(), postorder.begin() + inorderLeft.size());
        vector<int> postorderRight(postorder.begin() + inorderLeft.size(), postorder.end() - 1);

        mid->left = recursion(inorderLeft, postorderLeft);
        mid->right = recursion(inorderRight, postorderRight);

        return mid;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        auto root = recursion(inorder, postorder);
        return root;
    }
};

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

// 辅助函数：前序遍历打印树结构（用于验证）
void preorderPrint(TreeNode* root, vector<int>& result) {
    if (root == nullptr) {
        result.push_back(-1); // 用-1表示null
        return;
    }
    result.push_back(root->val);
    preorderPrint(root->left, result);
    preorderPrint(root->right, result);
}

// 辅助函数：中序遍历打印树结构（用于验证）
void inorderPrint(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    inorderPrint(root->left, result);
    result.push_back(root->val);
    inorderPrint(root->right, result);
}

// 辅助函数：后序遍历打印树结构（用于验证）
void postorderPrint(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    postorderPrint(root->left, result);
    postorderPrint(root->right, result);
    result.push_back(root->val);
}

// 辅助函数：打印向量
void printVector(const vector<int>& vec, const string& name) {
    cout << name << ": [";
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == -1) cout << "null";
        else cout << vec[i];
        if (i < vec.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 106. 从中序与后序遍历序列构造二叉树 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    cout << "\n测试案例1: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]" << endl;
    vector<int> inorder1 = {9, 3, 15, 20, 7};
    vector<int> postorder1 = {9, 15, 7, 20, 3};
    
    TreeNode* root1 = solution.buildTree(inorder1, postorder1);
    
    vector<int> preResult1, inResult1, postResult1;
    preorderPrint(root1, preResult1);
    inorderPrint(root1, inResult1);
    postorderPrint(root1, postResult1);
    
    cout << "输入: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]" << endl;
    printVector(preResult1, "前序遍历结果");
    printVector(inResult1, "中序遍历结果");
    printVector(postResult1, "后序遍历结果");
    cout << "期望: 构造出的树应该满足给定的中序和后序遍历" << endl;
    
    // 测试案例2: 示例2 - inorder = [-1], postorder = [-1]
    cout << "\n测试案例2: inorder = [-1], postorder = [-1]" << endl;
    vector<int> inorder2 = {-1};
    vector<int> postorder2 = {-1};
    
    TreeNode* root2 = solution.buildTree(inorder2, postorder2);
    
    vector<int> preResult2, inResult2, postResult2;
    preorderPrint(root2, preResult2);
    inorderPrint(root2, inResult2);
    postorderPrint(root2, postResult2);
    
    cout << "输入: inorder = [-1], postorder = [-1]" << endl;
    printVector(preResult2, "前序遍历结果");
    printVector(inResult2, "中序遍历结果");
    printVector(postResult2, "后序遍历结果");
    cout << "期望: 只有一个节点的树" << endl;
    
    // 测试案例3: 完全二叉树 - inorder = [4,2,5,1,6,3,7], postorder = [4,5,2,6,7,3,1]
    cout << "\n测试案例3: inorder = [4,2,5,1,6,3,7], postorder = [4,5,2,6,7,3,1]" << endl;
    vector<int> inorder3 = {4, 2, 5, 1, 6, 3, 7};
    vector<int> postorder3 = {4, 5, 2, 6, 7, 3, 1};
    
    TreeNode* root3 = solution.buildTree(inorder3, postorder3);
    
    vector<int> preResult3, inResult3, postResult3;
    preorderPrint(root3, preResult3);
    inorderPrint(root3, inResult3);
    postorderPrint(root3, postResult3);
    
    cout << "输入: inorder = [4,2,5,1,6,3,7], postorder = [4,5,2,6,7,3,1]" << endl;
    printVector(preResult3, "前序遍历结果");
    printVector(inResult3, "中序遍历结果");
    printVector(postResult3, "后序遍历结果");
    cout << "期望: 完全二叉树结构" << endl;
    
    // 测试案例4: 只有左子树 - inorder = [3,2,1], postorder = [3,2,1]
    cout << "\n测试案例4: inorder = [3,2,1], postorder = [3,2,1]" << endl;
    vector<int> inorder4 = {3, 2, 1};
    vector<int> postorder4 = {3, 2, 1};
    
    TreeNode* root4 = solution.buildTree(inorder4, postorder4);
    
    vector<int> preResult4, inResult4, postResult4;
    preorderPrint(root4, preResult4);
    inorderPrint(root4, inResult4);
    postorderPrint(root4, postResult4);
    
    cout << "输入: inorder = [3,2,1], postorder = [3,2,1]" << endl;
    printVector(preResult4, "前序遍历结果");
    printVector(inResult4, "中序遍历结果");
    printVector(postResult4, "后序遍历结果");
    cout << "期望: 左偏树结构" << endl;
    
    // 测试案例5: 只有右子树 - inorder = [1,2,3], postorder = [3,2,1]
    cout << "\n测试案例5: inorder = [1,2,3], postorder = [3,2,1]" << endl;
    vector<int> inorder5 = {1, 2, 3};
    vector<int> postorder5 = {3, 2, 1};
    
    TreeNode* root5 = solution.buildTree(inorder5, postorder5);
    
    vector<int> preResult5, inResult5, postResult5;
    preorderPrint(root5, preResult5);
    inorderPrint(root5, inResult5);
    postorderPrint(root5, postResult5);
    
    cout << "输入: inorder = [1,2,3], postorder = [3,2,1]" << endl;
    printVector(preResult5, "前序遍历结果");
    printVector(inResult5, "中序遍历结果");
    printVector(postResult5, "后序遍历结果");
    cout << "期望: 右偏树结构" << endl;
    
    // 测试案例6: 复杂不平衡树 - inorder = [1,3,2,4,5], postorder = [1,3,5,4,2]
    cout << "\n测试案例6: inorder = [1,3,2,4,5], postorder = [1,3,5,4,2]" << endl;
    vector<int> inorder6 = {1, 3, 2, 4, 5};
    vector<int> postorder6 = {1, 3, 5, 4, 2};
    
    TreeNode* root6 = solution.buildTree(inorder6, postorder6);
    
    vector<int> preResult6, inResult6, postResult6;
    preorderPrint(root6, preResult6);
    inorderPrint(root6, inResult6);
    postorderPrint(root6, postResult6);
    
    cout << "输入: inorder = [1,3,2,4,5], postorder = [1,3,5,4,2]" << endl;
    printVector(preResult6, "前序遍历结果");
    printVector(inResult6, "中序遍历结果");
    printVector(postResult6, "后序遍历结果");
    cout << "期望: 不平衡树结构" << endl;
    
    // 释放内存
    deleteTree(root1);
    deleteTree(root2);
    deleteTree(root3);
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    
    cout << "\n=== 测试完成 ===" << endl;
    cout << "\n注意：如果程序崩溃或结果不正确，可能是因为：" << endl;
    cout << "第33行应该使用 postorder.back() 而不是 *(postorder.end())" << endl;
    
    return 0;
}